import java.util.ArrayList;
import java.util.LinkedList;
import java.util.HashMap;
import java.util.Deque;
import java.util.List;
import java.util.Set;
import java.util.HashSet;

class Graph {
	private HashMap<String, ArrayList<String>> graph;
	public Graph() {
		graph = new HashMap<String, ArrayList<String>>();
	}

	public void insert (String str) {
		if (graph.containsKey(str)) {
			return;
		}

		ArrayList<String> str_adj  = new ArrayList<String>();
		for (String s : graph.keySet()) {
			if (distance(s, str) == 1) {
				graph.get(s).add(str);
				str_adj.add(s);
			}
		}
		graph.put(str, str_adj);
	}

	private int distance (String s, String t) {
		assert(s.length() == t.length());

		int count = 0;
		for (int i = 0; i <s.length(); ++i) {
			if (s.charAt(i) != t.charAt(i))
				++count;
		}

		return count;
	}

	private void printMap () {
		System.out.println(graph);
	}

	public List<List<String>> bfs (String start, String end, Set<String> dict) {
		HashMap<String, List<List<String>>> shortest_paths = new HashMap<String, List<List<String>>>();

		List<String> nstart = new LinkedList<String>();
		nstart.add(start);
		List<List<String>> nnstart = new LinkedList<List<String>>();
		nnstart.add(nstart);
		shortest_paths.put(start, nnstart);

		HashMap<String, Boolean> visited = new HashMap<String, Boolean>();

		visited.put(start, false);
		for (String s : dict) {
			visited.put(s, false);    
		}
		visited.put(end, false);


		Deque<String> last_level = new LinkedList<String>();
		Deque<String> next_level = new LinkedList<String>();
		last_level.add(start);

		boolean found = false;
		while (true) {
			while (last_level.size() != 0) {
				System.out.println(shortest_paths);

				if (shortest_paths.containsKey(end)) {
					found = true;
					break;			
				}

				String str = last_level.remove();
				visited.put(str, true);
				for (String s : graph.get(str)) {
					if (visited.get(s) == true) {
						continue;
					}
					System.out.println("afadf");

					if (!next_level.contains(s))
						next_level.add(s);

					if (!shortest_paths.containsKey(s))
						shortest_paths.put(s, new LinkedList<List<String>>());

					List<List<String>> last = shortest_paths.get(str);
					List<List<String>> now = shortest_paths.get(s);
					List<List<String>> temp = new LinkedList<List<String>>();

					for (List<String> l : last) {
						List<String> t = new LinkedList<String>();
						for (String st : l) {
							t.add(new String(st));
						}
						temp.add(t);
					}

					for (List<String> l : temp) {
						l.add(s);
						now.add(l);
					}
				}
			}

			if (found)
				break;
			last_level = next_level;
			next_level = new LinkedList<String>();
			if (last_level.size() == 0)
				break;
		}

		if (found)
			return shortest_paths.get(end);
		return new LinkedList<List<String>>();
	}
}

public class Solution {
	public List<List<String>> findLadders(String start, String end, Set<String> dict) {
		if (start.equals(end))
			return new LinkedList<List<String>>();

		Graph g = new Graph();
		g.insert(start);
		g.insert(end);
		for (String s : dict) {
			g.insert(s);
		}

		return g.bfs (start, end, dict);
	}

	public static void main(String[] args) {
		Solution s = new Solution();
		Set<String> set = new HashSet<String>();
		set.add("hot");
		set.add("dot");
		set.add("lot");
		set.add("dog");
		set.add("log");
		List<List<String>> result = s.findLadders("hit", "cog", set);
		System.out.println(result);
	}
}
